package problems

import (
	"math"
	"sort"
	"strconv"
)

// 501
// https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
func FindMode(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var modes []int
	var currentVal, currentCount, maxCount = root.Val, 0, 0
	var inOrder func(root *TreeNode)
	inOrder = func(root *TreeNode) {
		if root != nil {
			inOrder(root.Left)
			if root.Val == currentVal {
				currentCount++
			} else {
				currentVal = root.Val
				currentCount = 1
			}
			if currentCount == maxCount {
				modes = append(modes, root.Val)
			} else if currentCount > maxCount {
				maxCount = currentCount
				modes = []int{root.Val}
			}
			inOrder(root.Right)
		}
	}
	inOrder(root)
	return modes
}

// 504
// https://leetcode-cn.com/problems/base-7/
func ConvertToBase7(num int) string {
	if num == 0 {
		return `0`
	}
	var negative = num < 0
	var res []byte
	if negative {
		num = -num
	}

	for num > 0 {
		res, num = append([]byte(strconv.Itoa(num%7)), res...), num/7
	}
	if negative {
		res = append([]byte{'-'}, res...)
	}
	return string(res)
}

// 506
// https://leetcode-cn.com/problems/relative-ranks/
func FindRelativeRanks(score []int) []string {
	var max int
	for _, v := range score {
		if max < v {
			max = v
		}
	}
	mm := make([]int, max+1)
	for i := 0; i <= max; i++ {
		mm[i] = -1
	}
	for k, v := range score {
		mm[v] = k
	}
	res, rank := make([]string, len(score)), 1
	for i := max; i >= 0; i-- {
		if mm[i] > -1 {
			switch rank {
			case 1:
				res[mm[i]] = `Gold Medal`
			case 2:
				res[mm[i]] = `Silver Medal`
			case 3:
				res[mm[i]] = `Bronze Medal`
			default:
				res[mm[i]] = strconv.Itoa(rank)
			}
			rank++
		}
	}
	return res
}

// 507
// https://leetcode-cn.com/problems/perfect-number/
func CheckPerfectNumber(num int) bool {
	return map[int]bool{6: true, 28: true, 496: true, 8128: true, 33550336: true}[num]
}

// 509
// https://leetcode-cn.com/problems/fibonacci-number/
func Fib(N int) int {
	var a, b = 0, 1
	for N > 0 {
		a, b = b, a+b
		N--
	}
	return a
}

// 520
// https://leetcode-cn.com/problems/detect-capital/
func DetectCapitalUse(word string) bool {
	if len(word) < 2 {
		return true
	}
	secCase := 0
	if word[1] < 97 {
		secCase = 1
	}

	for i := 2; i < len(word); i++ {
		up := 0
		if word[i] < 97 {
			up = 1
		}
		if secCase^up == 1 {
			return false
		}
	}
	if word[0] >= 97 && secCase == 1 {
		return false
	}
	return true
}

// 521
// https://leetcode-cn.com/problems/longest-uncommon-subsequence-i/
func FindLUSlength(a string, b string) int {
	if a == b {
		return -1
	}
	if len(a) >= len(b) {
		return len(a)
	}
	return len(b)
}

// 530
// https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/
func GetMinimumDifference(root *TreeNode) int {
	var nodes []int
	var order func(root *TreeNode)
	order = func(root *TreeNode) {
		if root != nil {
			order(root.Left)
			nodes = append(nodes, root.Val)
			order(root.Right)
		}
	}
	order(root)
	var result = 0
	if len(nodes) > 0 {
		result = nodes[len(nodes)-1]
		var index, current = 1, 0
		for index < len(nodes) {
			current = nodes[index] - nodes[index-1]
			if current < result {
				result = current
			}
			index++
		}
	}
	return result
}

// 532
// https://leetcode-cn.com/problems/k-diff-pairs-in-an-array/
func FindPairs(nums []int, k int) int {
	sort.Ints(nums)
	var left, right, res = 0, 1, 0
	for right < len(nums) {
		if nums[right]-nums[left] > k {
			left++
		} else if nums[right]-nums[left] < k {
			right++
		} else {
			res++
			left++
			right++
			for right < len(nums) && nums[right] == nums[right-1] {
				right++
			}
		}
		if left == right {
			right++
		}
	}
	return res
}

// 538
// https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
func ConvertBST(root *TreeNode) *TreeNode {
	var order func(root *TreeNode)
	var sum = 0
	order = func(root *TreeNode) {
		if root != nil {
			order(root.Right)
			root.Val, sum = root.Val+sum, sum+root.Val
			order(root.Left)
		}
	}
	order(root)
	return root
}

// 541
// https://leetcode-cn.com/problems/reverse-string-ii/
func ReverseStr(s string, k int) string {
	start, end, sb := 0, 0, []rune(s)
	for i := 0; i <= len(sb)/k && i*2*k < len(sb); i++ {
		start, end = i*2*k, i*2*k+k-1
		if end > len(s)-1 {
			end = len(s) - 1
		}
		for start < end {
			sb[start], sb[end] = sb[end], sb[start]
			start++
			end--
		}
	}
	return string(sb)
}

// 543
// https://leetcode-cn.com/problems/diameter-of-binary-tree/
func DiameterOfBinaryTree(root *TreeNode) int {
	var diameter = 0
	var depth func(root *TreeNode) int
	depth = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		var left, right = depth(root.Left), depth(root.Right)
		if diameter < left+right {
			diameter = left + right
		}
		if left < right {
			left = right
		}
		return left + 1
	}
	depth(root)
	return diameter
}

// 551
// https://leetcode-cn.com/problems/student-attendance-record-i/
func CheckRecord(s string) bool {
	a, l := 0, 0
	for _, v := range s {
		switch v {
		case 'A':
			l = 0
			a++
		case 'L':
			l++
		default:
			l = 0
		}
		if a > 1 || l > 2 {
			return false
		}
	}

	return true
}

// 557
// https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
func ReverseWords(s string) string {
	start, res := -1, []byte(s)
	reverse := func(b []byte) {
		for i := 0; i < len(b)/2; i++ {
			b[i], b[len(b)-1-i] = b[len(b)-1-i], b[i]
		}
	}
	for i := 0; i < len(res); i++ {
		if res[i] == ' ' {
			reverse(res[start+1 : i])
			start = i
		}
	}
	reverse(res[start+1:])

	return string(res)
}

// 559
// https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/
func NodeMaxDepth(root *ChildNode) int {
	if root == nil {
		return 0
	}
	var depth = 0
	for _, v := range root.Children {
		var cDepth = NodeMaxDepth(v)
		if depth < cDepth {
			depth = cDepth
		}
	}
	return depth + 1
}

// 560
// https://leetcode-cn.com/problems/subarray-sum-equals-k/
func SubarraySum(nums []int, k int) int {
	var m = map[int]int{0: 1}
	var sum int
	var count int
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
		if v, ok := m[sum-k]; ok {
			count += v
		}
		m[sum]++
	}
	return count
}

// 561
// https://leetcode-cn.com/problems/array-partition-i/
func ArrayPairSum(nums []int) int {
	sort.Ints(nums)
	var sum = 0
	for i := 0; i < len(nums); i = i + 2 {
		sum += nums[i]
	}
	return sum
}

// 563
// https://leetcode-cn.com/problems/binary-tree-tilt/
func FindTilt(root *TreeNode) int {
	var tilt = 0
	var sum func(root *TreeNode) int
	sum = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		var left, right = sum(root.Left), sum(root.Right)
		tilt += int(math.Abs(float64(left - right)))
		return root.Val + left + right
	}
	sum(root)
	return tilt
}

// 566
// https://leetcode-cn.com/problems/reshape-the-matrix/
func MatrixReshape(nums [][]int, r int, c int) [][]int {
	if len(nums) == 0 || len(nums)*len(nums[0]) != r*c {
		return nums
	}
	var res [][]int
	var tmp []int
	xStart, yStart, xEnd, yEnd := 0, 0, c/len(nums[0]), c%len(nums[0])
	for i := 0; i < r; i++ {
		tmp = make([]int, 0)
		// 首行
		if xEnd > xStart {
			tmp = append(tmp, nums[xStart][yStart:]...)
		} else {
			tmp = append(tmp, nums[xStart][yStart:yEnd]...)
		}
		// 中间行
		for k := xStart + 1; k <= xEnd-1; k++ {
			tmp = append(tmp, nums[k]...)
		}
		// 末行
		if xEnd > xStart && xEnd < len(nums) {
			tmp = append(tmp, nums[xEnd][:yEnd]...)
		}
		res = append(res, tmp)
		xStart, yStart, xEnd, yEnd = xEnd, yEnd, xEnd+(c+yEnd)/len(nums[0]), (yEnd+c)%len(nums[0])
	}

	return res
}

// CheckInclusion
// 567
// https://leetcode-cn.com/problems/permutation-in-string/
func CheckInclusion(s1 string, s2 string) bool {
	l1 := len(s1)
	if l1 > len(s2) {
		return false
	}

	m := make(map[byte]int)
	for _, v := range s1 {
		m[byte(v)]++
	}

	for i := 0; i < len(s2); i++ {
		m[s2[i]]--
		if m[s2[i]] == 0 {
			delete(m, s2[i])
		}

		if i >= l1 {
			m[s2[i-l1]]++
			if m[s2[i-l1]] == 0 {
				delete(m, s2[i-l1])
			}
		}

		if len(m) == 0 {
			return true
		}
	}

	return false
}

// 572
// https://leetcode-cn.com/problems/subtree-of-another-tree/
func IsSubtree(s *TreeNode, t *TreeNode) bool {
	if t == nil {
		return true
	}
	var isSub = false
	var equal func(s *TreeNode, t *TreeNode) bool
	var order func(s *TreeNode)
	equal = func(s *TreeNode, t *TreeNode) bool {
		if s == nil && t == nil {
			return true
		}
		if s == nil || t == nil {
			return false
		}
		if s.Val != t.Val {
			return false
		}
		if !equal(s.Left, t.Left) || !equal(s.Right, t.Right) {
			return false
		}
		return true
	}
	order = func(s *TreeNode) {
		if !isSub && s != nil {
			if s.Left != nil {
				order(s.Left)
			}
			if s.Right != nil {
				order(s.Right)
			}
			if equal(s, t) {
				isSub = true
			}
		}
	}
	order(s)
	return isSub
}

// 575
// https://leetcode-cn.com/problems/distribute-candies/
func DistributeCandies(candyType []int) int {
	m := make(map[int]struct{})
	for _, v := range candyType {
		m[v] = struct{}{}
		if len(m) > len(candyType)/2 {
			return len(candyType) / 2
		}
	}
	if len(m) > len(candyType)/2 {
		return len(candyType) / 2
	}
	return len(m)
}

// 581
// https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/
func FindUnsortedSubarray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var length = len(nums)
	var leftStack, rightStack = make([]int, length-1), make([]int, length-1)
	for i := 0; i < length-1; i++ {
		if i == 0 {
			leftStack[i], rightStack[length-i-2] = nums[i], nums[length-i-1]
		} else {
			leftStack[i] = int(math.Max(float64(nums[i]), float64(leftStack[i-1])))
			rightStack[length-i-2] = int(math.Min(float64(nums[length-i-1]), float64(rightStack[length-i-1])))
		}
	}
	var left, right = 0, length - 1
	for left < right {
		if nums[left] > rightStack[left] && nums[right] < leftStack[right-1] {
			break
		} else if nums[left] <= rightStack[left] {
			left++
		} else {
			right--
		}
	}
	if left == right {
		return 0
	}
	return right - left + 1
}

// 589
// https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal/
func PreOrder(root *ChildNode) []int {
	var res []int
	if root == nil {
		return res
	}
	var stack = []*ChildNode{root}
	for len(stack) > 0 {
		var node = stack[len(stack)-1]
		res = append(res, node.Val)
		stack = stack[:len(stack)-1]
		for i := len(node.Children) - 1; i >= 0; i-- {
			stack = append(stack, node.Children[i])
		}
	}
	return res
}

// 590
// https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
func PostOrder(root *ChildNode) []int {
	var res []int
	if root == nil {
		return res
	}
	var stack = []*ChildNode{root}
	for len(stack) > 0 {
		var node = stack[len(stack)-1]
		if len(node.Children) == 0 {
			res = append(res, node.Val)
			stack = stack[:len(stack)-1]
		} else {
			for i := len(node.Children) - 1; i >= 0; i-- {
				stack = append(stack, node.Children[i])
			}
			node.Children = nil
		}
	}
	return res
}

// 594
// https://leetcode-cn.com/problems/longest-harmonious-subsequence/
func FindLHS(nums []int) int {
	m := make(map[int]int)
	for _, v := range nums {
		if _, ok := m[v]; !ok {
			m[v] = 0
		}
		m[v]++
	}
	max := 0
	for num, count := range m {
		if v, ok := m[num-1]; ok {
			if max < count+v {
				max = count + v
			}
		}
		if v, ok := m[num+1]; ok {
			if max < count+v {
				max = count + v
			}
		}
	}
	return max
}

// 598
// https://leetcode-cn.com/problems/range-addition-ii/
func MaxCount(m int, n int, ops [][]int) int {
	x, y := m, n
	for _, op := range ops {
		if op[0] < x {
			x = op[0]
		}
		if op[1] < y {
			y = op[1]
		}
	}
	return x * y
}

// 599
// https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/
func FindRestaurant(list1 []string, list2 []string) []string {
	m, min := make(map[string]int), len(list1)+len(list2)+1
	for k, v := range list1 {
		m[v] = k
	}
	var res []string
	for k, v := range list2 {
		if _, ok := m[v]; ok {
			m[v] += k
			if min > m[v] {
				min, res = m[v], []string{v}
			} else if min == m[v] {
				res = append(res, v)
			}
		}
	}
	return res
}
